package com.njupt.backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/12 10:57
 * @Description: 17. 电话号码的字母组合
 * @Version: 1.0
 */


public class LetterCombinations {

    public List<String> letterCombinations(String digits) {
        Map<Integer, String> stringMap = new HashMap<>();
        stringMap.put(2, "abc");
        stringMap.put(3, "def");
        stringMap.put(4, "ghi");
        stringMap.put(5, "jkl");
        stringMap.put(6, "mno");
        stringMap.put(7, "pqrs");
        stringMap.put(8, "tuv");
        stringMap.put(9, "wxyz");
        int startIndex = 0;
        int len = digits.length();
        List<String> results = new ArrayList<>();
        if (len == 0) {
            return results;
        }

        StringBuilder sb = new StringBuilder();
        backtracking(startIndex, len, results, sb, stringMap, digits);
        return results;
    }

    private void backtracking1(int startIndex, int len, List<String> results, StringBuilder sb, Map<Integer, String> stringMap, String digits) {
        if (sb.length() == len) {
            results.add(sb.toString());
            return;
        }

        for (int i = startIndex; i < len; i++) {
            String s = stringMap.get(digits.charAt(i) - '0');
            for (int j = 0; j < s.length(); j++) {
                sb.append(s.charAt(j));
                backtracking1(i + 1, len, results, sb, stringMap, digits);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    private void backtracking(int startIndex, int len, List<String> results, StringBuilder sb, Map<Integer, String> stringMap, String digits) {
        if (sb.length() == len) {
            results.add(sb.toString());
            return;
        }

        int i = digits.charAt(startIndex) - '0';
        String s = stringMap.get(i);
        for (int j = 0; j < s.length(); j++) {
            sb.append(s.charAt(j));
            backtracking(startIndex + 1, len, results, sb, stringMap, digits);
            sb.deleteCharAt(sb.length() - 1);
        }


    }

    public static void main(String[] args) {
        LetterCombinations test = new LetterCombinations();
        List<String> strings = test.letterCombinations("23");
        System.out.println(strings);
    }
}
